package com.openess.bigsearch.engine.utils.sort;

import java.util.Comparator;

/**
 * 插入排序
 * 
 * @author TuTu
 * 
 * @param <E>
 */
public class InsertionSort<E> implements Sort<E> {
	/**
	 * 对数组进行插入排序
	 * 
	 * @param array
	 *            待排数组
	 * @param p
	 *            起始位置
	 * @param r
	 *            终止位置(包括)
	 */
	public void sort(E[] array, int p, int r, Comparator<? super E> c) {
		// 程序从第二个值开始，始终假设j前面的所有值都是已排序的，A[j]在前面已排序的值之中找到合适的插入点，通过移位将值进行插入
		for (int j = p + 1; j <= r; j++) {
			E key = array[j];
			// p~i是已排序部分，j~r是待排序部分
			int i = j - 1;
			// 将元素依次移位，准备插入新元素，如果相等就不移位，保证了稳定性
			while (i >= p && c.compare(array[i], key) > 0) {
				array[i + 1] = array[i];
				i--;
			}
			// i+1是插入位置
			array[i + 1] = key;
		}
	}
}
